package pers.tz.题目;

import static pers.tz.common.ArrayUtils.*;

/**
 * 给定一个数组，求n-m位置的元素的和
 * @author irony
 * @date 2024-03-09
 */
public class 数组前缀和 {
    public static void main(String[] args) {
        int[] ints = generateRandomArray();
        printArray(ints);

        System.out.println(accumulate(ints, 1, 3));
        System.out.println(accumulate2(ints, 1, 3));
    }

    // 可行解:每次获取累加和都遍历数组累加
    public static int accumulate(int[] ints, int start, int end) {
        int sum = 0;
        for (; start <= end; start++) {
            sum += ints[start];
        }
        return sum;
    }

    // 最优解：先维护出一个前缀和数组
    public static int accumulate2(int[] ints, int start, int end) {
        int[] preSumArr = new int[ints.length];
        int preSum = 0;
        for (int i = 0; i < ints.length; i++) {
            preSum += ints[i];
            preSumArr[i] = preSum;
        }

        // 然后获取累加和，只需要从前缀和数组中获取，进行减法
        return preSumArr[end] - preSumArr[start - 1];
    }
}
